package questionSolution.Question_438;

import java.util.*;

public class Solution_1 {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        HashMap<String, List<Integer>> map = new HashMap<>();
        int lp = p.length();
        char[] pp = p.toCharArray();
        Arrays.sort(pp);
        String key = new String(pp);
        for (int i = 0; i < s.length() - p.length() + 1; i++) {
            String s1 = s.substring(i, i+lp);
            char[] c1 = s1.toCharArray();
            Arrays.sort(c1);
            String s2 = new String(c1);
            if (!map.containsKey(s2)){
                map.put(s2, new ArrayList<>());
            }
            map.get(s2).add(i);
        }
        if(map.containsKey(key)){
            ans =  map.get(key);
        }
        return ans;
    }

    static void main() {
        Solution_1 S = new Solution_1();
        String s = "cbaebabacd";
        String p = "cba";
        List<Integer> ans = S.findAnagrams(s, p);
        System.out.println(ans);
    }
}
